The present invention generally relates to content addressable memories (CAMs) and more particularly to an improved CAM design that includes distinct boundaries at the matchline latches, allowing the matchlines and priority encoder to be completely tested.
Content-Addressable Memories (CAMs) are used in applications where some known data may be stored in a memory but the address of the memory location holding the data is unknown. While CAMs may take on a number of forms, the simplest is a circuit similar in many ways to a Static Random Access Memory (SRAM), with the addition of a search function. During a search, data is provided via inputs to the memory which is then compared with the data in each address of the entire memory array (or some subset of the entire array) which will result in a xe2x80x9cMatchxe2x80x9d (or xe2x80x9cHitxe2x80x9d) for those words (individual memory entries) whose stored data is bitwise equal to the incoming data and a xe2x80x9cMismatchxe2x80x9d (or xe2x80x9cMissxe2x80x9d) for those words whose stored data differs by one or more bits to the incoming data. The results of the match are placed onto the matchlines, of which one exists for each word.
In prior embodiments of CAM designs, including those embedded CAMs used in ASIC design systems, the individual matchline outputs typically have not been available directly, but rather are made available to the user through a priority encoder, which prioritizes the addresses of all matching words and returns the single address which has the highest priority, along with a hit/miss signal which is active only if there is at least one matching word (note that some CAMs also include a multiple hit signal which is active only if there is more than one matching word). Differing priority schemes can be used, including returning the highest or the lowest matching address, and each scheme has concerns which affect the testability and, more specifically, the test patterns which are used to test the search function of the CAM.
For instance, suppose a CAM has 64 words and a priority encoder which returns the lowest matching memory address. A logical representation of this CAM is shown in FIG. 1. Block S represents the control section of the CAM which receives a clock 1, address inputs 2, and control inputs 3, along with any test-related input or output signals 4. When the clock 1 is active during a read or write the local address 6 (which may be a multiplexed version of the functional and test address inputs) is sent to the wordline decoders and drivers 7, which turns on one of the wordlines 8, of which there is one for each word in the memory array 9. During a write operation, data is inputted through the data inputs 12 (and can be masked on a bitwise basis by bit-write mask inputs 20) into the write drivers 11 which drive the data onto the bidirectional read/write/search bitlines 14 and into the selected word. During a read operation, data is read from the selected word onto the differential read/write/search bitlines 14 into the sense amps (also 11) and through to the data outputs 13. During testing, the data 13 is also sent back to the control 5 where it is compared with the expected data contained in the test inputs 4. These operations are essentially the same as for a standard 1-port memory array.
When the clock 1 is active during a search operation, no wordline inputs 8 to the array 9 are selected. Instead, a search clock signal 21 is sent to every word in the array. Search data is inputted through the data inputs 12 (and can be masked on a bitwise basis by search mask inputs 20) into the write drivers 11 and onto the differential read/write/search bitlines 14. The data is then compared to every word in the array 9 during the active portion of the search clock 21, and the precharged matchlines 15 for every word are driven low (for a mismatch) or stay high (for a match) and latched in the matchline latches 23 whose outputs 22 are then sent into the priority encoder 16. The priority encoder 16 encodes the lowest matching address onto search address outputs 17, along with a hit/miss signal 18 and a multiple hit detect signal 19.
During test, all three of the outputs 17-19 from the priority encoder are also sent back to the control section 5 where they are compared with the expected value(s) contained in test inputs 4. This places limitations on the types of tests performed on the CAM. The only way to observe the outputs of a search operation during test is through these outputs. A mismatch on every word is simple to detect. A simple test is to write a xe2x80x9c0xe2x80x9d into every bit of every word of the memory array, then walk a xe2x80x9c1xe2x80x9d across a field of xe2x80x9c0xe2x80x9d s in the search data. For example, FIG. 2 shows a table which demonstrates the test sequence for a CAM which has 64 words with an 8-bit wide word.
The test sequences in FIG. 2 cause a single-bit mismatch for each bit in every word (note that each search is implied to be all addresses). Each word is expected to mismatch for every search and, thus, if any word has a defect which causes it to match, the hit/miss signal will go active, causing the CAM to indicate that a fail has occurred. The test is repeated, writing a xe2x80x9c1xe2x80x9d to the entire array and marching a xe2x80x9c0xe2x80x9d across a field of xe2x80x9c1xe2x80x9ds.
Testing for a match on every word, however, is more difficult, and when testing through a priority encoder cannot be done in a single cycle (and can never be done exhaustively), a xe2x80x9cpull-the-blindsxe2x80x9d approach is used, where the test is begun at the highest order address and proceeds to subsequently lower order addresses. FIG. 3 shows graphically a representation of the sequence in which the searches occur for a 64-word CAM whose priority encoder returns the lowest matching address.
In FIG. 3, the test begins by writing some data into the entire array (e.g., xe2x80x9c0xe2x80x9d) to every cell. In the first cycle (a), some different data is written into the highest order address (word 63) (e.g., xe2x80x9c1xe2x80x9d) to every cell in this word. A search is then conducted for the data in word 63, resulting in a match on this word. The address xe2x80x9c63xe2x80x9d appears as the output of the priority encoder and the hit/miss signal is set active to indicate that a match has occurred. This xe2x80x9cwrite followed by searchxe2x80x9d sequence is repeated for each word in the CAM. For example, in subsequent cycles (b), the same new data (all xe2x80x9c1xe2x80x9d) is written into and searched from each next lower address. On each subsequent search, multiple words match the data, but only the lowest matching address appears at the output of the priority encoder (e.g., word 52), and the hit/miss indicates a match. It should be evident that words 63-53 are now being xe2x80x9cmaskedxe2x80x9d by the priority encoder, and if there is some defect which causes any of words 63-53 to indicate a mismatch during a match on some other word, when it should actually be matching, the fault would go undetected.
To date, this has been a problem of untestability in all CAMs which provide match outputs as a priority encoded address; however, it is not generally considered to be a major limitation since the priority encoder is still functional as promised, in that it returns the lowest matching address. Embedded CAM designs which directly provide the match outputs are tested by a means other than selftest. Typically, functional test methods are used which are very costly to develop. methodology have, to date, contained priority encoders and have not directly offered matchline outputs due to the above-described test limitations.
In view of the foregoing and other problems, disadvantages, and drawbacks of the conventional CAMs, the present invention has been devised, and it is an object of the present invention to provide a structure and method for an improved CAM design.
In order to attain the objects suggested above, there is provided, according to one aspect of the invention, a content addressable memory structure which includes a memory array of words, each word has multiple memory bits. The invention includes a plurality of matchlines, each being connected to one of the words, and a self-test matchline compare circuit connected to the matchlines, adapted to individually test the match function for all of the words. Further, the invention includes a matchline compare circuit which has a plurality of comparators equal in number to the number of words, such that each word is connected to a dedicated comparator to allow each word in the memory array to be individually tested. The matchline compare circuit has first latches connected to the matchlines and second latches adapted to store compare data. The comparators are connected to the first latches and the second latches, and are adapted to compare data in the first latches with the second latches. The structure includes an equal number of words and first latches, such that each matchline is connected to a dedicated first latch. An override signal line is connected to the comparators and the comparators compare data in the first latches with data on the override signal line. The multiplexors are connected to the override signal line, the second latches, and the comparators. The control signal line is connected to the multiplexors, wherein the control signal line supplies a control signal that selects, as inputs, one of the override signal line and the second latches to be output from the multiplexors to the comparators. The structure includes an equal number of the words, the first latches, the second latches, the multiplexors, and the comparators, such that each word""s match function is individually tested. The override signal line carries a test data pattern that does not match data in any word in the memory array.
The invention creates a distinct boundary at the matchline latches, allowing the matchlines to be completely tested during BIST and the priority encoder to be completely tested by logic test (providing the best test coverage of both circuits at an optimum cost savings).